package stack;

import java.util.Stack;

public class Solution {
    public static int evalRPN (String[] tokens) {
        Stack<String> stack = new Stack<>();
        int ret = 0;
        int i = 0;
        int x = 0;
        int y = 0;
        while (i != tokens.length) {
            //数字就push
            if (!isOperation(tokens[i])) {
                stack.push(tokens[i]);
            }
            //运算符就pop并执行运算
            else {
                //x转为数字
                x = Integer.parseInt(stack.pop());
                y = Integer.parseInt(stack.pop());
                switch (whichOperation(tokens[i])) {
                    case 1:
                        y += x;
                        break;
                    case 2:
                        y -= x;
                        break;
                    case 3:
                        y *= x;
                        break;
                    case 4:
                        y /= x;
                        break;
                }
                //x转为String后push
                stack.push(String.valueOf(y));
            }
            i++;
        }
        ret = Integer.parseInt(stack.pop());
        return ret;
    }

    public static boolean isOperation (String s) {
        if (s == "+" || s == "-" || s == "*" || s == "/") {
            return true;
        }
        return false;
    }

    public static int whichOperation (String s) {
        if (s == "+") {
            return 1;
        } else if (s == "-") {
            return 2;
        } else if (s == "*") {
            return 3;
        } else {
            return 4;
        }
    }

    public static boolean IsPopOrder (int[] pushA, int[] popA) {
        Stack<Integer> stack = new Stack<>();
        int x = 0;
        for (int i = 0; i < pushA.length; i++) {
            stack.push(pushA[i]);
            while (x < popA.length && !stack.empty() && stack.peek().equals(popA[x])) {
                 x++;
                 stack.pop();
            }
        }
        return stack.empty();
    }

    public static void main(String[] args) {
        int[] a = {1};
        int[] b = {2};
        boolean i = IsPopOrder(a,b);
        System.out.println(i);
    }
    public static boolean isValid (String s) {
        Stack<Character> stack = new Stack<>();

        //字符串转数组
        char[] strings = s.toCharArray();
        int c = 0;
        //第一个就是右括号可以直接结束了
        if (strings[0] == ')' || strings[c] == '}' || strings[c] == ']' ) {
            return false;
        }

        //遍历数组
        while (c != s.length()) {
            //左括号就push进栈
            if (strings[c] == '(' || strings[c] == '{' || strings[c] == '[') {
                stack.push(strings[c]);
                c++;
            }
            //右括号就和栈顶括号匹配
            else {
                //左括号
                char x = strings[c];
                //匹配失败或者栈为空就false
                switch (x) {
                    case ')' : {
                        if (stack.empty() || stack.pop() != '(') {
                            return false;
                        }
                        break;
                    }
                    case ']' : {
                        if (stack.empty() || stack.pop() != '[') {
                            return false;
                        }
                        break;
                    }
                    case '}' : {
                        if (stack.empty() || stack.pop() != '{') {
                            return false;
                        }
                        break;
                    }
                }
                c++;
            }
        }
        if (stack.empty()) {
            return true;
        }
        return false;
    }

    public static void main2(String[] args) {
        String[] tokens = new String[] {"2","1", "+", "3", "*"};
        int ret = Solution.evalRPN(tokens);
        System.out.println(ret);
    }

    public static void main1(String[] args) {
//        String s = "()(){}";
//        System.out.println(Solution.isValid(s));
//        System.out.println();
//        s = "())";
//        System.out.println(Solution.isValid(s));
//        System.out.println();
        String s = "{[]}";
        boolean b = Solution.isValid(s);
        System.out.println(b);
    }
}
